/**
 * problem_015.c
 * Copyright (C) 2011-03-18 - xrose
 * How many routes are there through a 20×20 grid
 * Answer is: chinh hop lap voi tan so cho truoc:
 * (k1+k2+..+kn)!/(k1!*k2!*..kn!)
 * in this problem: Ans = 40!/(20!*20!)
 */

#include <stdio.h>
#include <gmp.h>

int main (int argc, char *argv[])
{
    mpz_t gt40, gt20, tmp;
    mpz_init(gt40);
    mpz_init(gt20);
    mpz_init(tmp);

    mpz_set_d(gt20, 1);
    int i;
    for (i=1; i<=20; i++)
    {
        mpz_mul_ui(gt20, gt20, i);
    }
    mpz_set(gt40, gt20);
    for(i=21; i<=40; i++)
    {
        mpz_mul_ui(gt40, gt40, i);
    }

    mpz_out_str(stdout, 10, gt20);
    puts("");
    mpz_out_str(stdout, 10, gt40);
    mpz_mul(tmp, gt20, gt20);
    mpz_divexact(gt40, gt40, tmp);
    puts("\n-----");
    mpz_out_str(stdout, 10, gt40);
    return 0;
}
